package com.c2b.algorithm.newcoder.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=295&tqId=23452&ru=%2Fpractice%2F947f6eb80d944a84850b0538bf0ec3a5&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj">对称的二叉树</a>
 * <p>给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）</p>
 * 例如：
 * <pre>
 *     // 下面这棵二叉树是对称的
 *               1
 *             /  \
 *            2    2
 *          /  \  / \
 *         3   4 4   3
 *
 *     //  下面这棵二叉树不对称。
 *                1
 *              /  \
 *             2    2
 *              \    \
 *               3    3
 * </pre>
 * 数据范围：节点数满足0≤n≤1000，节点上的值满足∣val∣≤1000<br>
 * 要求：空间复杂度O(n)，时间复杂度O(n)<br>
 * 备注：你可以用递归和迭代两种方法解决这个问题<br>
 *
 * @author c2b
 * @since 2023/3/14 13:46
 */
public class BM0031IsSymmetrical_S {

    /**
     * 迭代.借助两个辅助栈
     */
    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(pRoot.left);
        queue2.offer(pRoot.right);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            // 分别从两个队列中弹出元素
            final TreeNode left = queue1.poll();
            final TreeNode right = queue2.poll();
            // 都为空暂时对称
            if (left == null && right == null) {
                continue;
            }
            // 某一个为空或者val不相等不对称
            if (left == null || right == null || left.val != right.val) {
                return false;
            }
            // queue1从左往右加入队列
            queue1.offer(left.left);
            queue1.offer(left.right);
            // queue2从右往左加入队列
            queue2.offer(right.right);
            queue2.offer(right.left);
        }
        return true;
    }

    /**
     * 递归
     */
    boolean isSymmetrical2(TreeNode pRoot) {
        return recursion(pRoot, pRoot);
    }

    private boolean recursion(TreeNode a, TreeNode b) {
        if (a == null && b == null) {
            return true;
        }
        if (a == null || b == null || a.val != b.val) {
            return false;
        }
        return recursion(a.left, b.right) && recursion(b.left, a.right);

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        BM0031IsSymmetrical_S bm0031IsSymmetrical_s = new BM0031IsSymmetrical_S();
        System.out.println(bm0031IsSymmetrical_s.isSymmetrical2(root));
    }
}
